def solve(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
    dp = [0] * (W + 1)  # dp[j] 表示容量为 j 时的最大价值

    # 遍历所有物品
    for i in range(n):
        # 从后往前遍历背包容量，避免重复使用同一物品
        for j in range(W, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

    return dp[W]  # 返回背包容量为 W 时的最大价值

if __name__ == "__main__":
    n, W = map(int, input().split())
    weights = []
    values = []
    for _ in range(n):
        weight, value = map(int, input().split())
        weights.append(weight)
        values.append(value)

    print(solve(weights, values, W))
